package backTrack;

import java.util.*;

public class ds40 {
    public static void main(String[] args) {
        System.out.println(combinationSum2(new int[]{2,5,2,1,2}, 5));
    }
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<>();
        int[] used = new int[candidates.length];
        track(ans, path, candidates, target, 0, 0, used);
        return ans;
    }
    public static void track(List<List<Integer>> ans, List<Integer> path, int[] candidates, int target, int sum, int index, int[] used){
        if(sum > target || index > candidates.length)
            return;
        if(sum == target){
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            if(i > 0 && (candidates[i] == candidates[i - 1]) && used[i - 1] == 0)
                continue;
            path.add(candidates[i]);
            used[i] = 1;
            track(ans, path, candidates, target, sum + candidates[i], i + 1, used);
            path.remove(path.size() - 1);
            used[i] = 0;
        }
    }
}
